package leetcode.N601_N700;


import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/12/11 6:00 下午
 */
public class N649 {

    public static void main(String[] args) {
        N649 n = new N649();
        System.out.println(n.predictPartyVictory("RD"));
    }

    public String predictPartyVictory(String senate) {
        int length;
        if (senate == null || (length = senate.length()) == 0) {
            return null;
        }
        Queue<Integer> dire = new ArrayBlockingQueue<>(length);
        Queue<Integer> radiant = new ArrayBlockingQueue<>(length);
        // 构建双方人员
        for (int i = 0; i < length; i++) {
            if (senate.charAt(i) == 'R') {
                radiant.add(i);
            } else {
                dire.add(i);
            }
        }
        // 开始团战
        while (!dire.isEmpty() && !radiant.isEmpty()) {
            // 双方都还有人 则开始战斗
            Integer sf = dire.poll();
            Integer am = radiant.poll();
            if (sf > am) {
                radiant.add(am + length);
            } else {
                dire.add(sf + length);
            }
            int ds = dire.size();
            int rs = radiant.size();
            if (ds >= (rs << 1)) {
                return "Dire";
            } else if (rs >= (ds << 1)) {
                return "Radiant";
            }
        }
        return dire.isEmpty() ? "Radiant" : "Dire";
    }


}
